/**
 * 有三种魔法球、十种技能，每种技能都是三种魔法球的组合（可重复）。
 * 现在需要连续释放技能，但是手中只能持有三个魔法球，且必须按照队列性质
 * 例如需要连续释放技能1和2，则首先持有三个魔法球，记作
 * a1 a2 a3
 * 释放技能1。随后，如果a1a2a3不是技能2的组合，则必须先拿掉a1, 追加a4
 * 可以自由选择追加的魔法球。
 * 此时手中持有变为了：a2a3a4
 * 如果能满足施法，即可完成。
 * 否则必须扔掉a2，追加a5。
 * 还不行的话就扔掉a3，追加a6。此时必然可以释放技能2。
 * 
 * 手中持有必须按顺序，但是技能构成无需按顺序。
 * 例如假设输入给定技能1的构成是a3a2a1，则手中持有a1a2a3一样可以释放技能1
 * 
 * 现在给定N个技能的序列，两种操作：
 * 1. s e: 问连续释放[s, e]区间内的技能，最少需要依次那几个魔法球，每次施法之初手中都是空的
 * 2. p x: 将第p个位置的技能修改为x
 * 
 * 首先释放第一个技能必须拿3个球，然后考虑后续。
 * 从技能a到技能b，需要追加的球的数量显然与a魔法球以及b魔法球的排列有关。
 * 一个技能最多可能存在6种不同的排列。
 * 因此令 Dijuv 记录技能i的排列u后面跟技能j的排列v时需要改变的数量。
 * 所以D是一个10*10*6*6的四维数组，可以预处理出来。
 * 
 * 再考虑一段连续的释放，首先考虑[1...n]，令Znu表示从1释放到n的最少数量，且以n的u排列结尾。
 * 则： Znu = min(Z[n-1][v] + D[n-1][n][v][u], v是n-1的所有排列状态)
 * 则  min{Znu, u是n的所有排列}为所求。
 * 将Zn看作是列向量，将Dij看做是矩阵，可以将规划方程写成矩阵形式
 *   Zn = D[n-1][n] * Z[n - 1]
 * 其中 `*` 表示矩阵的类乘操作
 * 
 * 于是N个魔法球，有N-1个衔接，有N-1个矩阵，用线段树维护这N-1个矩阵的累乘积。
 * 修改操作自然包含其中。
 */
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

template <typename T>
const T & mymin(const T & a, const T & b){
    return min(a, b);
}

template<typename T, typename ... Args>
const T & mymin(const T & t, const Args & ... args){
    return min(t, mymin(args ...));
}

struct SegTree{ // 线段树带延迟

using llt = int;

int N;

struct value_type {
    array<array<llt, 6>, 6> data;
    array<llt, 6> & operator [] (int p) {return data[p];}
    const array<llt, 6> & operator [] (int p) const {return data[p];}

    value_type() = default;
    value_type(const array<array<llt, 6>, 6> & b):data(b){}

    bool isNull() const {
        return data[0][0] < 0;
    }

    const value_type operator * (const value_type & rhs) const {
        value_type ans;
        for(int i=0;i<6;++i){
            auto & r = ans[i];
            auto & d = data[i];
            for(int j=0;j<6;++j){
                r[j] = mymin(
                    d[0] + rhs[0][j], 
                    d[1] + rhs[1][j], 
                    d[2] + rhs[2][j], 
                    d[3] + rhs[3][j], 
                    d[4] + rhs[4][j],
                    d[5] + rhs[5][j]
                );
            }
        }
        return ans;
    }
};

vector<value_type> data; // 线段树

using lazy_type = value_type;
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    // assert(0);
    if(ls.isNull()) return rs;
    if(rs.isNull()) return ls;

    return ls * rs;
}

/// 从上往下计算信息，要变动
void _dn_(int t, int s, int e, const lazy_type & delta) {
    // assert(0);
    copy(delta.data.begin(), delta.data.end(), data[t].data.begin());
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    // lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int a, int b, const lazy_type & delta){
    _modify(1, 1, N, a, b, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 这个函数不用动
void build(int n, const value_type a[]) {
    _build(1, 1, n, a);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }
    // _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    value_type ans = value_zero(); // 如果求最值，这里不能用zero
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int a, int b, const lazy_type & delta) {
    if(a <= s and e <= b) {
        _dn_(t, s, e, delta);
        return;
    }
    // _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    if(a <= mid) _modify(lson(t), s, mid, a, b, delta);
    if(mid < b) _modify(rson(t), mid + 1, e, a, b, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 这个函数几乎不用动
void _pushDown(int t, int s, int e) {
    // if(lazy_zero() == lazy[t]) return;
    // auto & lz = lazy[t];
    // auto ls = lson(t), rs = rson(t);
    // int mid = (s + e) >> 1;

    // _dn_(ls, s, mid, lz);
    // _dn_(rs, mid + 1, e, lz);

    // lz = lazy_zero();
}


/// 几乎不用动
void _build(int t, int s, int e, const value_type a[]) {
    if(s == e) {
        data[t] = a[s]; // 注意提供value_type的初始化
        return; 
    }
    int mid = (s + e) >> 1;
    _build(lson(t), s, mid, a);
    _build(rson(t), mid + 1, e, a);
    _pushUp(t);
}

/// 辅助函数，视延迟的类型而变动
static const lazy_type & lazy_zero() {
    static const lazy_type LAZY0{};
    return LAZY0; 
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0(array<array<llt, 6>, 6>{-1});
    return VALUE0;
}

static llt inf() {
    static const llt INF = 0x6F7F8F9F;
    return INF;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};

array<array<int, 3>, 10> JI {
    array<int, 3>{0, 0, 0},
    {0, 0, 1},
    {0, 0, 2},
    {2, 2, 2},
    {2, 2, 0},
    {2, 2, 1},
    {1, 1, 1},
    {1, 1, 0},
    {1, 1, 2},
    {2, 0, 1}
};

using matrix_t = SegTree::value_type;

matrix_t D[10][10];

ostream & operator << (ostream & os, const matrix_t & r){
    for(const auto & a : r.data){
        for(auto i : a){
            os << i << " ";
        }
        os << endl;
    }
    return os;
}

int proc(const array<int, 3> & a, const array<int, 3> & b){
    if(a[0] == b[0] and a[1] == b[1] and a[2] == b[2]) return 0;
    if(a[1] == b[0] and a[2] == b[1]) return 1;
    if(a[2] == b[0]) return 2;
    return 3;
}

void proc(int a, int b){
    auto sa = JI[a];
    auto sb = JI[b];
    auto & d = D[a][b];

    for(int i=0;i<6;++i,next_permutation(sa.begin(), sa.end())){
        auto & di = d[i];
        for(int j=0;j<6;++j,next_permutation(sb.begin(), sb.end())){
            di[j] = proc(sa, sb);
        }
    }
    return;
}

void init(){
    for(auto & a : JI) sort(a.begin(), a.end());

    for(int a=0;a<10;++a){
        for(int b=0;b<10;++b){
            proc(a, b);
            // cout << "(" << a << ", " << b << "): \n";
            // cout << D[a][b] << endl;
        }
    }

    return;
}

SegTree St;
int N, M;
vector<int> A;
vector<matrix_t> B;

void work(){
    init();

    cin >> N >> M;
    A.assign(N + 1, {});
    for(int i=1;i<=N;++i) cin >> A[i], --A[i];

    B.clear(); B.reserve(N); B.emplace_back(matrix_t());
    for(int i=1;i<N;++i) B.emplace_back(D[A[i]][A[i + 1]]);

    if(1 == N){
        for(int c,x,y,q=1;q<=M;++q){
            cin >> c >> x >> y;
            if(1 == c) cout << "3\n";            
        }        
        return;
    }

    St.init(N - 1);
    St.build(N - 1, B.data());

    for(int c,x,y,q=1;q<=M;++q){
        // cout << "Problem " << q << ":" << endl;
        cin >> c >> x >> y;
        if(1 == c){
            if(x == y){
                cout << "3\n"; continue;
            }
            auto ans = St.query(x, y - 1);
            // cout << "[" << x << ", " << y << "]\n";
            // cout << ans << endl;
            auto tmp = SegTree::inf();
            for(const auto & a : ans.data){
                tmp = mymin(tmp, a[0], a[1], a[2], a[3], a[4], a[5]);
            }
            cout << tmp + 3 << "\n";
        }else{
            A[x] = --y;
            if(x > 1) St.modify(x - 1, x - 1, D[A[x - 1]][y]);
            if(x < N) St.modify(x, x, D[y][A[x + 1]]);
        }
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase;
    while(nofkase--) work();
    return 0;
}